#include "mergesort.hpp"

// merge two sorted array (low-mid) and (mid+1-high) into one
static void merge (vector<int> &a, int low, int mid, int high)
{
    int i, j, k;

    if (debug)
        cout << "merge " << low << "-" << mid << "-" << high << endl;

    if (mid < low || mid >= high) {
        cout << "range error"
             << " low=" << low
             << " mid=" << mid
             << " high=" << high << endl;
        return;
    }

    // initialize vector
    vector<int> a_l(a.begin() + low, a.begin() + mid + 1);
    vector<int> a_r(a.begin() + mid + 1, a.begin() + high + 1);
    // merge into array a
    i = j = 0; k = low;
    while (i < (mid-low+1) && j < (high-mid))
    {
        if ( a_l[i] < a_r[j] ) {
            a[k++] = a_l[i++];
        } else {
            a[k++] = a_r[j++];
        }
    }
    while (i < mid-low+1)
        a[k++] = a_l[i++];
    while (j < high-mid)
        a[k++] = a_r[j++];
}

// merge sort of a list of integers
// @a input array reference

static void mergesortHelper(vector<int> &a, int low, int high)
{
    // range check
    if (high <= low) return;
    int mid = (low + high) / 2;
    mergesortHelper(a, low, mid);
    mergesortHelper(a, mid+1, high);
    merge(a, low, mid, high);
}

void mergesort(vector<int> &a)
{
    int low = 0;
    int high = a.size() -1;
    if (high == 0 || high == 1) return;

    if (debug)
        cout << "merge sort " << low << "-" << high << endl;

    mergesortHelper(a, low, high);
}
